# 作者：小七
# 2025年01月07日

import random
import time
import sys

sys.setrecursionlimit(1000000)  # 增加递归深度


class Sort:
    def __init__(self, n):
        self.len = n
        self.arr = [0] * n
        self.random_data()

    def random_data(self):
        for i in range(self.len):
            self.arr[i] = random.randint(1, 99)

    def partition(self, left, right):
        arr = self.arr
        k = i = left
        for i in range(left, right):
            if arr[i] < arr[right]:
                arr[i], arr[k] = arr[k], arr[i]
                k += 1
        arr[k], arr[right] = arr[right], arr[k]
        return k

    def quick_sort(self, left, right):
        if left < right:
            pivot = self.partition(left, right)
            self.quick_sort(left, pivot - 1)
            self.quick_sort(pivot + 1, right)

    def adjust_max_heap(self, pos, arr_len):
        arr = self.arr
        dad = pos
        son = 2 * dad + 1
        while son < arr_len:
            if son + 1 < arr_len and arr[son + 1] > arr[son]:
                son += 1
            if arr[son] > arr[dad]:
                arr[son], arr[dad] = arr[dad], arr[son]
                dad = son
                son = 2 * dad + 1
            else:
                break

    def heap_sort(self):
        for parent in range(self.len // 2 - 1, -1, -1):
            self.adjust_max_heap(parent, self.len)
        arr = self.arr
        arr[0], arr[self.len - 1] = arr[self.len - 1], arr[0]
        for arr_len in range(self.len - 1, 1, -1):
            self.adjust_max_heap(0, arr_len)
            arr[0], arr[arr_len-1] = arr[arr_len-1], arr[0]

    def test_time_use(self, sort_func, *args,**kwargs):
        start = time.time()
        sort_func(*args,**kwargs)
        end = time.time()
        print(f"{sort_func.__name__} time use: {end - start}s")


if __name__ == '__main__':
    my_sort = Sort(10)
    print(my_sort.arr)
    my_sort.quick_sort(0, len(my_sort.arr) - 1)
    print(my_sort.arr)
    my_sort=Sort(10000)
    my_sort.test_time_use(my_sort.quick_sort, 0, len(my_sort.arr) - 1)
    my_sort.test_time_use(my_sort.heap_sort)


